# coding=utf-8

# 定义一个整数二叉前缀树，因为整数可以使用二进制表示
# 整数采用二进制格式的小端法存储到树种，小端法即高位在右，低位在左
class IntTrie(object):
	"""an abstract definition of int trie"""
	def __init__(self):
		self.left = self.right = None
		self.value = None

def insert(tree,key,value=None):
	"""
	向整数二叉前缀树插入数值key，以及存储的节点值，value可以为None
	"""
	if tree is None:
		tree = IntTrie()
	p = tree
	while key != 0: # 每一次遍历都会向子树进一层
		if key & 1 == 0: # & 1操作实质上是取最低位的数字
			if p.left is None:
				p.left = IntTrie()
			p = p.left
		else:
			if p.right is None:
				p.right = IntTrie()
			p = p.right
		key = key >> 1  # 右移一位，删除最低位
	p.value = value
	return tree

def lookup(tree,key):
	if tree is None:
		return None
	p = tree
	while key != 0:
		# print('key='+str(key))
		if key & 1 == 0:
			if p.left is None:
				return None
			p = p.left
			# print('left')
		else:
			if p.right is None:
				return None
			p = p.right
			# print('right')
		key = key >> 1
	return p

# 递归形式的lookup
def lookup_recursive(tree,key):
	if tree is None:
		return None
	if key == 0:
		return tree
	if key & 1 == 0:
		# 如果最低位是0，在左子树中查找 
		return lookup_recursive(tree.left,key>>1)
	else:
		return lookup_recursive(tree.right,key>>1)


if __name__ == '__main__':
	t = insert(None,4,4)
	print(t.left.left.right.value)
	result = lookup(t,4)
	print(result.value)
	t = insert(t,9,"hello")
	print(lookup(t,9).value)
	print(lookup_recursive(t,9).value)

		